МОДЕЛЬ

ВЫБОР НАИЛУЧШИХ ВАРИАНТОВ ИЗ БАЗ ДАННЫХ

С.В.Микони, Р.В.Козченко, П.Г.Созоновский

Санкт-Петербургский государственный университет путей сообщения

e-mail: mikoni@pgups.spb.ru

Abstract –– In present work the relationship is determined between a different theoretic choosing methods. The presented specialized choice system realizes all known methods of optimal variants choosing from data bases of different types.

1. Введение

Наибольший интерес в базах данных представляют не сами фактические данные, а извлекаемое из них знание. С этой целью, начиная с ранних версий, системы управления базами данных (СУБД) оснащаются различными функциями обработки данных. Они позволяют решать следующие типовые задачи анализа данных:

1) вычисление производных показателей;

2) поиск экземпляров с экстремальным значением показателя;

3) вычисление среднего значения показателя;

4) ранжирование экземпляров данных относительно значения показателя;

5) выделение данных, соответствующих заданным требованиям;

6) сегментация данных относительно близких значений показателя;

7) выявление зависимости между показателями, характеризующими экземпляры данных;

8) выбор наилучших вариантов относительно заданных критериев.

Настоящий период развития баз данных характеризуется:

1) увеличением объёмов хранимых данных (хранилища данных);

2) применением универсальных средств доступа к данным (SQL-server);

3) обеспечением удобства анализа данных с использованием модели гиперкуба (OLAP-service);

4) применением разнообразных графических средств отображения данных;

5) специализацией обработки на конкретные применения.

Обработка данных стала характеризоваться понятиями из области искусственного интеллекта: data mining и knoledge discovery, трактуемыми как интеллектуальный анализ данных. Предназначенные для его выполнения информационные системы характеризуются универсальностью, разнообразием решаемых задач и разветвлённым интерфейсом. Однако эти достоинства имеют и оборотную сторону. Универсальные системы чрезмерно сложны и нетехнологичны для неквалифицированного пользователя, неполно используются им в силу избыточности относительно конкретного применения, занимают большой объём памяти. Типичным примером такого рода систем является пакет Excel, входящий в состав Microsoft Office. Наряду с другими функциями обработки данных он позволяет выполнять сортировку и фильтрацию данных. Эти функции необходимы, но недостаточны для реализации всех классических методов выбора наилучших вариантов в дискретном пространстве данных.

В докладе излагается подход к обработке баз данных, основанный на парадигме “универсальности внутри специализации” на примере задачи выбора наилучших вариантов из баз данных (система выбора).

2. Характеристика системы

Система выбора специализируется только на функциях выбора наилучших вариантов и в тоже время является универсальной по отношению к базам данных различного типа и известным методам выбора, причём пользователь системы не обязан знать специфику этих методов. В его задачу входит формулирование условий выбора, а система в соответствии с ними должна автоматически выбирать приемлемый метод, реализуя процедуру вывода. Это позволяет отнести систему к классу интеллектуальных систем поддержки принятия решений. Указанный подход требует нахождения взаимосвязи методов выбора путём выявления их сходства и различий, что является теоретической частью работы. Практическая часть работы предусматривает выбор эффективного инструментария построения системы, разработку простого и технологичного интерфейса и реализацию всех методов выбора.

Поскольку методы выбора, реализуемые системой, используют ранговую шкалу, они ориентированы на обработку числовой информации. Однако, в базах данных наряду с числовыми широко используются лингвистические переменные, измеряемые лишь по номинальной шкале. Для участия атрибутов баз данных с лингвистическими переменными в выборе наилучших вариантов возможно использование процедур фильтрации (селекции) и упорядочения (ранжирования). Первая из них естественна для номинальной шкалы. В множество допустимых вариантов включаются только помеченные значения лингвистической переменной. Для использования процедуры упорядочения необходимо ранжировать значения лингвистической переменной. Для оценочной переменной такое ранжирование естественно. Например, значения “низкая”, “средняя”, “высокая” (эргономичность) можно проранжировать целыми числами по возрастанию, начиная с нуля (0,1,2). Это делается вручную при анализе атрибутов на предмет рассмотрения их в качестве критериев оценки вариантов. Для не оценочных лингвистических переменных ранжирование может применяться как искусственный приём.

3. Систематизация методов выбора

Наиболее распространёнными являются две группы методов: ординального и кардинального выбора. Первая группа методов выполняет упорядочение n вариантов - бинарное R² I X? X (метод попарных сравнений), либо n-арное R^nIX? ...? X (n сомножителей). Упорядочение выполняется группой экспертов. Из их индивидуальных оценок находится групповая.

Вторая группа методов основана на критериальной оценке альтернатив и включает следующие основные методы:

отбор недоминируемых альтернатив (метод Парето);
условная оптимизация с ограничениями по равенству и неравенству;
поиск альтернатив с заданными свойствами (метод притязаний);
поиск альтернатив относительно упорядоченных по важности критериев (метод приоритета критериев);
метод уступок (более важного критерия в пользу менее важного);
поиск наилучших вариантов относительно суперкритерия (свёртки нескольких критериев в один общий).

Каждый критерий может максими-зироваться или минимизироваться.

Различение методов с целью их автоматического выбора достигается применением процедуры вывода. Последняя представима моделью дерева, каждой терминальной (висячей) вершине которого ставится в соответствие метод выбора.

Для решения этой задачи необходимо охарактеризовать каждый метод значениями управляющих переменных, имеющих смысл классифи-кационных признаков (оснований деления) для каждого яруса дерева вывода. К ним относятся следующие переменные:

множество атрибутов Y, характе-ризующих каждый вариант предметного знания;

множество пометок M атрибутов, выбираемых для оценки вариантов;

множество атрибутов Z, для которых задаются ограничения из множества C;

множество атрибутов Q=Y\Z, используемых в качестве критериев оптимизации;

направление оптимизации Min/Max для критериев и ограничений для задания неравенств <, ? ., >, ? ;

множество приоритетов (мест) критериев P со значениями, обратно пропорциональными важности крите-риев;

множество весов критериев A (B );

признак запроса пары вариантов для их сопоставления R.

Признаком, различающим группы методов ординального и кардинального упорядочения, является множество пометок M. Если представители первой группы не требуют анализа атрибутов Y, они характеризуются отсутствием пометок атрибутов: M=? . Запрос пары вариантов для их сопоставления (R=true) означает выбор метода попарного сравнения.

Методы кардинального упорядочения характеризуются наличием выбранных атрибутов: M? ? . Между собой методы этой группы различаются следующими признаками:

1. Метод притязаний

1) Y= Z - все выбранные атрибуты являются ограничениями;

2) Min =? и Max =? - все ограничения по равенству.

2. Множество допустимых вариантов X_доп

1) Y= Z - все выбранные атрибуты являются ограничениями;

2) Min ? ? и/или Max ? ? - все ограничения по неравенству.

3. Метод Парето

1) Y=Q - все выбранные атрибуты являются критериями;

2) для каждого y_iIY задано направление оптимизации (Min/Max);

3) для всех критериев не заданы веса:

A =? (B =? );

4) для всех критериев не заданы приоритеты: P =? .

4. Метод приоритетов

1) Y=Q - все выбранные атрибуты являются критериями;

2) для каждого y_iIY задано направление оптимизации (Min/Max);

3) для всех критериев не заданы веса: A =? (B =? );

4) для всех критериев заданы приоритеты: P ? ? .

5. Метод уступок

Выполняется после метода приоритетов при задании следующей дополнительной информации:

1) критерия y_i, значение которого следует улучшить;

2) величины уступки в процентах (по умолчанию 5%).

6. Метод суперкритерия

1) Y=Q - все выбранные атрибуты являются критериями;

2) для каждого y_iIY задано направление оптимизации (Min/Max);

3) для всех критериев заданы веса:

A =? (B =? );

4) если S b _i =1, то свёртка критериев -

i = 1

мультипликативная, иначе - аддитивная.

7. Однокритериальная оптимизация

1) Y? Z - не все выбранные атрибуты являются ограничениями;

2) i Qi =1 - один атрибут выбран в качестве критерия.

8. Многокритериальная оптимизация

1) Y? Z - не все выбранные атрибуты являются ограничениями;

2) i Qi >1 - более, чем один атрибут выбран в качестве критерия;

3) относительно выбранных критериев Y в зависимости от задания для них весов A (B ) или приоритетов P реализуются метод суперкритерия или приоритетов, а при A (B )=? и P =? - метод Парето.

4. Прототип системы выбора

Главное меню системы состоит из 5-ти разделов:

Предметная область (ПО);

Атрибуты выборки (данных);

Варианты выборки;

Выбранные варианты;

Экспертные методы.

Содержимое раздела ПО составляет совокупность предметных областей, включённых в собственную базу данных системы из предметных баз.

Раздел “Атрибуты выборки” включает перечень атрибутов, характеризующих варианты знания выбранной ПО. Для каждого атрибута вычисляются верхняя и нижняя границы. Если атрибут участвует в выборе, определяется его роль (ограничение/критерий). Если он выбран в качестве ограничения, то задаётся граница (снизу/сверху/точно) и значение границы. Если атрибут играет роль критерия, то задаётся его направленность (min/max) и значимость (независимый/место/вес).

В разделе “Варианты выборки” осуществляется просмотр значений атрибутов, характеризующих каждый вариант, а в разделе “Выбранные варианты” приводится выбранное подмножество вариантов.

Раздел “Экспертные методы” предусматривает ранжирование вариантов выборки (при ограниченном их числе) экспертами и вычисление групповых оценок.

Прототип системы разработан в среде Borland C++ Builder 3. Доступ к внешним данным осуществляется с помощью Borland DataBase Engine (BDE) и драйверов Open DataBase Connectivity (ODBC). Для каждой СУБД разрабатывается свой конвертор дан-ных.

К “мягкости” выбора в разработанной системе можно отнести участие в выборе лингвистических признаков, характеризующих варианты, а также возможность использования коэффициентов уверенности в экспертных оценках вариантов.

В отличие от ряда фирменных систем, реализующих процедуры выбора по принципу “снизу-вверх” на основе таких типовых операций, как сортировка, фильтрация, поиск экстремума, рассматриваемая система выбора разработана по принципу “сверхувниз” - от всех известных методов выбора к реализующим их операциям обработки массивов данных. Этот подход и обеспечил такие свойства системы, как простоту и универсальность относительно методов выбора, иллюстрируя известную истину: “нет ничего практичнее хорошей теории”.

Литература

1. Рощупкина Б.Д., Шапот М.Д. Интеллектуальный анализ данных в бизнес- приложениях: подход фирмы Cognos. Новости ИИ. -М.: Ассоциация ИИ, 1997, №4.

2. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. -М.: Высшая школа, 1989.

2. Микони С.В. Методы и алгоритмы принятия решений. Учебное пособие. Часть 1. -СПб.: ПГУПС. 1995.

3. Микони С.В. Универсальная система выбора. Тезисы конференции “Новые информационные технологии в региональной инфраструктуре”. - Астрахань: АГТУ, 1997.

Site of Information Technologies
Designed by inftech@webservis.ru.